#ifndef HEAP_HPP
#define HEAP_HPP

#include <utility>

template <class Less, class Swap>
class min_heap
{
    size_t _size;   /* number of elements */
    Less _less;     /* comparer function */
    Swap _swap;     /* swap function */

    static size_t Left(size_t i) { return 2*i+1; }
    static size_t Right(size_t i) { return 2*i+2; }
    static size_t Parent(size_t i) { return (i-1)/2; }
    
    void heapify(size_t i)
    {
        for (;;)
        {
            size_t large = i;
            size_t left = Left(i), right = Right(i);
            if (left < _size && _less(left, large))
                large = left;
            if (right < _size && _less(right, large))
                large = right;
            if (large == i)
                break;
            _swap(i, large);
            i = large;
        }
    }

public:
    min_heap(const Less &less = Less(), const Swap &swap = Swap())
        : _size(0), _less(less), _swap(swap) { }

    /* Returns the numer of elements in the heap. */
    size_t size() const { return _size; }

    /* Returns true if the heap is empty. */
    bool empty() const { return _size == 0; }

    /* Moves the top element to the end of the heap and decreases the size
     * of the heap by 1.
     */
    void pop()
    {
        _swap(0, _size - 1);
        if (--_size != 0)
            heapify(0);
    }

    /* Updates the heap structure after decreasing the value of a given 
     * element. */
    void promote(size_t index)
    {
        while (index != 0 && _less(index, Parent(index)))
        {
            _swap(index, Parent(index));
            index = Parent(index);
        }
    }

    /* Appends an element to the end of the heap. */
    void push()
    {
        ++_size;
        promote(_size - 1);
    }
};

#endif /* HEAP_HPP */
